package leetcode_1001_1100;

import java.util.Arrays;

public class LeeCode_1187_timeout {
    public static void main(String[] args) {
        System.out.println(makeArrayIncreasing(new int[]{1, 5, 3, 6, 7}, new int[]{1, 3, 2, 4}));
        System.out.println(makeArrayIncreasing(new int[]{1, 5, 3, 6, 7}, new int[]{4, 3, 1}));
        System.out.println(makeArrayIncreasing(new int[]{1, 5, 3, 6, 7}, new int[]{1, 6, 3, 3}));
        System.out.println(makeArrayIncreasing(new int[]{1, 5, 3}, new int[]{4,1}));
        System.out.println(makeArrayIncreasing(new int[]{19,18,7,4,11,8,3,10,5,8,13},
                new int[]{13,16,9,14,3,12,15,4,21,18,1,8,17,0,3,18}));
        System.out.println(makeArrayIncreasing(new int[]{5,16,19,2,1,12,7,14,5,16},
                new int[]{6,17,4,3,6,13,4,3,18,17,16,7,14,1,16}));
    }
    private static int makeArrayIncreasing(int[] arr1, int[] arr2) {
        int n = arr1.length;
        int[] mins = new int[n];
        Arrays.sort(arr2);
        mins[n - 1] = Integer.MAX_VALUE;
        int min = Integer.MAX_VALUE;
        for (int i = n - 2; i >= 0; i--) {
            if (arr1[i + 1] < min){
                min = arr1[i + 1];
            }
            mins[i] = min;
        }
        int[] ans = new int[1];
        ans[0] = Integer.MAX_VALUE;
        dfs(arr1, arr2, mins, 0, ans, 0);
        return ans[0] == Integer.MAX_VALUE ? -1 : ans[0];
    }

    private static void dfs(int[] arr1, int[] arr2, int[] mins,int now, int[] ans, int from) {
        for (int i = from; i < arr1.length; i++) {
            int pre = -1;
            if (i != 0){
                pre = arr1[i - 1];
            }
            if (arr1[i] <= pre){
                int index = getRight(arr2, pre);
                if (index == -1){
                    return;
                }
                arr1[i] = arr2[index];
                now++;
            }else if (arr1[i] >= mins[i]){
                int index = getRight(arr2, pre);
                if (index == -1)
                    continue;
                if (arr2[index] < arr1[i]){
                    dfs(Arrays.copyOf(arr1, arr1.length), arr2, mins, now, ans, from + 1);
                    arr1[i] = arr2[index];
                    now++;
                }
            }
        }
        ans[0] = Math.min(ans[0], now);
    }

    private static int getRight(int[] arr2, int min){
        for (int i = 0; i < arr2.length; i++) {
            int num = arr2[i];
            if (num > min){
                return i;
            }
        }
        return -1;
    }
}
